#include <vector>
#include <iostream>

using namespace std;

class Solution {
private:
    int get_num(vector<vector<int>>& board, int i, int j) {
        if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size()) {
            return 0;
        }
        return board[i][j];
    }

    int get_side_num(vector<vector<int>>& board, int i, int j) {
        return get_num(board, i - 1, j - 1) + get_num(board, i - 1, j) + get_num(board, i - 1, j + 1) + get_num(board, i, j - 1) + get_num(board, i, j + 1) + get_num(board, i + 1, j - 1) + get_num(board, i + 1, j) + get_num(board, i + 1, j + 1);
    }

    void dfs(vector<vector<int>>& board, vector<vector<bool>>& visited, int i, int j) {
        if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || visited[i][j]) {
            return;
        }
        int next = board[i][j];
        if (board[i][j]) {
            int alive_num = get_side_num(board, i, j);
            if (alive_num < 2) {
                next = 0;
            } else if (alive_num <= 3) {
                next = 1;
            } else {
                next = 0;
            }
        } else {
            int alive_num = get_side_num(board, i, j);
            if (alive_num == 3) {
                next = 1;
            }
        }
        visited[i][j] = true;
        dfs(board, visited, i - 1, j - 1);
        dfs(board, visited, i - 1, j);
        dfs(board, visited, i - 1, j + 1);
        dfs(board, visited, i, j - 1);
        dfs(board, visited, i, j + 1);
        dfs(board, visited, i + 1, j - 1);
        dfs(board, visited, i + 1, j);
        dfs(board, visited, i + 1, j + 1);
        board[i][j] = next;
    }
public:
    void gameOfLife(vector<vector<int>>& board) {
        if (board.size() == 0 || board[0].size() == 0) {
            return;
        }
        int height = board.size();
        int width = board[0].size();
        vector<vector<bool>> visited(height, vector<bool>(width, false));
        dfs(board, visited, 0, 0);
    }
};

int main() {
    vector<vector<int>> input = {
            {0, 1, 0},
            {0, 0, 1},
            {1, 1, 1},
            {0, 0, 0}
    };
    Solution solution;
    solution.gameOfLife(input);
    cout << endl;
}